package ai.zixing.mashibing.basic_class.class05;

import java.util.HashMap;

public class Code02_TrieTree {
    public static class Node1 {
        // 每通过一个就++
        public int pass;
        // 尾字符节点
        public int end;
        // 下级的路
        public Node1[] nexts;

        public Node1() {
            pass = 0;
            end = 0;
            // 创建26条，0-a,2-b,25-z
            // nexts[i] == null 则i方向的路不存在
            nexts = new Node1[26];
        }
    }

    public static class Trie1{
        private Node1 root;

        public Trie1() {
            root = new Node1();
        }

        // 插入
        public void insert(String word) {
            if (word == null) {
                return;
            }
            char[] chs = word.toCharArray();
            Node1 node = root;
            node.pass++;
            // 遍历字符串中的字符
            int index = 0;
            for (int i = 0; i < chs.length; i++) {
                int path = chs[i] - 'a';
                // 如果之间没有则创建
                if (node.nexts[path] == null) {
                    node.nexts[path] = new Node1();
                }
                node = node.nexts[path];
                node.pass++;
            }
            node.end++;
        }

        // word 之间加入过几次
        public int searcher(String word) {
            if (word == null) {
                return 0;
            }
            char[] chs = word.toCharArray();
            Node1 node = root;
            int index = 0;
            for (int i = 0; i < chs.length; i++) {
                index = chs[i] - 'a';
                if (node.nexts[index] == null) {
                    return 0;
                }
                node = node.nexts[index];
            }
            return node.end;
        }

        public void delete(String word) {
            // 存在才删除
            // 如只存在abc，但是删除abcd，则有问题，必须先判断已经加入过了
            if (searcher(word) != 0) {
                char[] chs = word.toCharArray();
                Node1 node = root;
                // 头节点
                node.pass--;
                int index = 0;
                for (char ch : chs) {
                    index = ch - 'a';
                    // pass 为 0  则表示后面的没用了，置空
                    // 如已经添加 abc, abcdf,如果删除abcdf则d的pass为0，后续之间置空
                    if (--node.nexts[index].pass == 0) {
                        node.nexts[index] = null;
                        return;
                    }
                    node = node.nexts[index];
                }
                node.end--;
            }
        }

        // 所有加入的字符串中，有几个是以 pre 这个字符串为前缀的
        public int prefixNumber(String pre) {
            if (pre == null) {
                return 0;
            }
            char[] chs = pre.toCharArray();
            Node1 node = root;
            int index = 0;
            for (char ch : chs) {
                index = ch - 'a';
                if (node.nexts[index] == null) {
                    return 0;
                }
                node = node.nexts[index];
            }
            return node.pass;
        }
    }

    public static class Node2 {
        public int pass;
        public int end;
        // 字符不只是小写字母
        public HashMap<Integer, Node2> nexts;

        public Node2() {
            pass = 0;
            end = 0;
            nexts = new HashMap<>();
        }
    }

    public static class Trie2{
        private Node2 root;

        Trie2() {
            root = new Node2();
        }

        public void insert(String word) {
            if (word == null) {
                return;
            }
            char[] chs = word.toCharArray();
            Node2 node = root;
            node.pass++;
            int index = 0;
            for (char ch : chs) {
                index = ch - 'a';
                if (!node.nexts.containsKey(index)) {
                    node.nexts.put(index, new Node2());
                }
                node = node.nexts.get(index);
                node.pass++;
            }
            node.end++;
        }

        public int searcher(String word) {
            if (word == null) {
                return 0;
            }
            char[] chs = word.toCharArray();
            Node2 node = root;
            int index = 0;
            for (char ch : chs) {
                index = ch - 'a';
                if (!node.nexts.containsKey(index)) {
                    return 0;
                }
                node = node.nexts.get(index);
            }
            return node.end;
        }

        public int prefixNumber(String pre) {
            if (pre == null) {
                return 0;
            }
            char[] chs = pre.toCharArray();
            Node2 node = root;
            int index = 0;
            for (char ch : chs) {
                index = ch - 'a';
                if (!node.nexts.containsKey(index)) {
                    return 0;
                }
                node = node.nexts.get(index);
            }
            return node.pass;
        }

        public void delete(String word) {
            if (searcher(word) != 0) {
                char[] chs = word.toCharArray();
                Node2 node = root;
                node.pass--;
                int index = 0;
                for (char ch : chs) {
                    index = ch - 'a';
                    if (--node.nexts.get(index).pass == 0) {
                        node.nexts.remove(index);
                        return;
                    }
                    node = node.nexts.get(index);
                }
                node.end--;
            }
        }
    }

    public static class Right{
        private HashMap<String, Integer> box;

        public Right() {
            this.box = new HashMap<>();
        }

        public void insert(String word) {
            box.put(word, box.getOrDefault(word, 0) + 1);
//            if (!box.containsKey(word)) {
//                box.put(word, 1);
//            } else {
//                box.put(word, box.get(word) + 1);
//            }
        }

        public void delete(String word) {
            if (box.containsKey(word)) {
                if (box.get(word) == 1) {
                    box.remove(word);
                } else {
                    box.put(word, box.get(word) - 1);
                }
            }
        }

        public int searcher(String word) {
            return box.getOrDefault(word, 0);
        }

        public int prefixNumber(String pre) {
            int count = 0;
            for (String cur : box.keySet()) {
                if (cur.startsWith(pre)) {
                    count += box.get(cur);
                }
            }
            return count;
        }
    }

    public static String generateRandomString(int strLen) {
        char[] chs = new char[(int) (Math.random() * strLen)];
        for (int i = 0; i < chs.length; i++) {
            int value = (int) (Math.random() * 6);
            chs[i] = (char) (97 + value);
        }
        return String.valueOf(chs);
    }

    public static String[] generateRandomStringArray(int arrLen, int strLen) {
        String[] ans = new String[(int)(Math.random() * strLen)];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = generateRandomString(strLen);
        }
        return ans;
    }

    public static void main(String[] args) {
        int arrLen = 200;
        int strLen = 20;
        int testTimes = 100000;
        for (int i = 0; i < testTimes; i++) {
            String[] arr = generateRandomStringArray(arrLen, strLen);
            Trie1 trie1 = new Trie1();
            Trie2 trie2 = new Trie2();
            Right right = new Right();
            for (int j = 0; j < arr.length; j++) {
                double decide = Math.random();
                if (decide < 0.25) {
                    trie1.insert(arr[j]);
                    trie2.insert(arr[j]);
                    right.insert(arr[j]);
                } else if (decide < 0.5) {
                    trie1.delete(arr[j]);
                    trie2.delete(arr[j]);
                    right.delete(arr[j]);
                } else if (decide < 0.75) {
                    int ans1 = trie1.searcher(arr[j]);
                    int ans2 = trie2.searcher(arr[j]);
                    int ans3 = right.searcher(arr[j]);
                    if (ans1 != ans2 || ans2 != ans3) {
                        System.out.println("Oops!");
                    }
                } else {
                    int ans1 = trie1.prefixNumber(arr[j]);
                    int ans2 = trie2.prefixNumber(arr[j]);
                    int ans3 = right.prefixNumber(arr[j]);
                    if (ans1 != ans2 || ans2 != ans3) {
                        System.out.println("Oops!");
                    }
                }
            }
        }
        System.out.println("finish!");
    }
}
